#include <iostream>
using namespace std;

#include "ProgCommon.h"
#include "MaxHeap.h"


#define N 7

struct Point {
    Point( int tx = 0, int ty = 0 )
    {
        x = tx;
        y = ty;
    }

    Point( const Point &that )
    {
        x = that.x;
        y = that.y;
    }

    Point& operator=( const Point &that )
    {
        if ( this != &that ) {
            x = that.x;
            y = that.y;
        }

        return *this;
    }

    operator int() const
    {
        return x;
    }


    int x, y;
};

int n;
Point W[N+1];
Point B[N+1];

template<class T>
void SelectSort( T a[], int n )
{
    int i, j, k;
    for ( i = 1; i < n; i++ ) {
        k = i;
        for ( j = i + 1; j <= n; j++ ) {
            if ( a[j] < a[k] )
                k = j;
        }
        if ( k != i )
            Swap( a[i], a[k] );
    }
}

bool canControl( Point &a, Point &b )
{
    if ( a.x >= b.x && a.y >= b.y )
        return true;

    return  false;
}

bool hasPoint( Point S[], int n, int x, int y )
{
    int i;
    for ( i = 1; i <= n; i++ ) {
        if ( S[i].x == x && S[i].y == y )
            return true;
    }

    return  false;
}

void fillPoint( Point S[], int n )
{
    int i = 1;
    while ( i <= n ) {
        int tx = RandomInt( 1, 10 );
        int ty = RandomInt( 1, 10 );
        if ( i == 1 || !hasPoint( S, i-1, tx, ty ) )
            S[i++] = Point( tx, ty );
    }

}

void Show( Point a[],  int n )
{
    for ( int i = 1; i <= n; i++ ) {
        printf( "(%d, %d) ", a[i].x, a[i].y );
    }
}


int main()
{
    PROG_BANNER;
    RAND_SEED;

    ConSetColor( FG_CYAN );
    printf( "Prog 8 : BlackWhite\n" );
    ConSetColor( COLOR_DEFAULT );

    n = N;

    fillPoint( W, n );
    fillPoint( B, n );

    SelectSort( W, n );
    MaxHeap<Point> H( 1 );

    printf( "Black >>\n  " );
    Show( W, n );
    printf( "\nWhite >>\n  " );
    Show( B, n );
    printf( "\n" );

    printf( "\nResult >>\n" );
    H.Initialize( B, n, n );
    int visited[N+1] = {0};
    int cnt = 0, i, j;
    Point v;
    for ( i = n; i >= 1; i-- ) {
        H.DeleteMax( v );
        // printf( " -(%d, %d)- ", v.x, v.y );
        for ( j = 1; j <= n; j++ ) {
            if ( 0 == visited[j] ) {
                if ( canControl( W[j], v ) ) {
                    printf( " * (%d, %d) control (%d, %d)\n",
                            W[j].x, W[j].y,
                            v.x, v.y );
                    visited[j] = 1;
                    cnt++;
                    break;
                }
            }
        }
    }

    printf( "Final count is %d", cnt );

    H.Deactivate();
    printf( "\n" );
    PROG_BANNER;
    PROG_PAUSE;
}

